package it.luigiarpino.kernighanLin.bipartition;

import java.util.HashSet;
import java.util.Random;
import java.util.Set;

/**
 * Calcola il bipartizionamento secondo Leen Kernighan
 * 
 * precondizioni:
 * 	la matrice deve essere quadrata di dimansione 2n
 * 	la matrice deve essere simmetrica
 * 
 * @author Luigi Lorenzo Arpino
 * 
 *
 */
public class LKBipartitionEnhanced 
{
	public static void main(String[] args)
	{
		/*
		int[][] matrix={
				   //0  1  2  3  4  5  
					{0, 0, 0, 0, 1, 0 },// 0
					{0, 0, 0, 0, 0, 1 },// 1
					{0, 0, 0, 0, 1, 0 },// 2
					{0, 0, 0, 0, 0, 1 },// 3
					{1, 0, 1, 0, 0, 1 },// 4
					{0, 1, 0, 1, 1, 0 },// 5
			};
		*/
		
		int[][] matrix={
			    //   0  1  2  3  4  5  6  7
					{0, 0, 1, 0, 0, 0, 0, 0 },// 0
					{0, 0, 1, 0, 0, 0, 0, 0 },// 1
					{1, 1, 0, 1, 1, 0, 0, 0 },// 2
					{0, 0, 1, 0, 0, 0, 0, 0 },// 3
					{0, 0, 1, 0, 0, 1, 1, 1 },// 4
					{0, 0, 0, 0, 1, 0, 0, 0 },// 5
					{0, 0, 0, 0, 1, 0, 0, 0 },// 6
					{0, 0, 0, 0, 1, 0, 0, 0 },// 7
			};
		
		/*
		int[][] matrix={
			    //   0  1  2  3 
					{0, 0, 1, 0},//0
					{0, 0, 1, 0},//1
					{1, 1, 0, 1},//2
					{0, 0, 1, 0},//3
			};
		*/
		
		LKBipartitionEnhanced lk=new LKBipartitionEnhanced(matrix,10);
		int costo=lk.getCosto();
		int[] partA=lk.getOptimalPartitionA();
		int[] partB=lk.getOptimalPartitionB();
		int[] partizionamento=lk.getPartizionamento();
		System.out.println();
		System.out.println("costo="+costo);
		System.out.println();
		System.out.println("Partition A");
		for(int i=0; i< partA.length ; i++)
	    {
			System.out.print(" "+partA[i]);
	    }
		System.out.println();
		System.out.println("Partition B");
		for(int i=0; i< partB.length ; i++)
	    {
			System.out.print(" "+partB[i]);
	    }
		System.out.println();
		System.out.println("Partizionamento");
		for(int i=0; i< partizionamento.length ; i++)
	    {
			System.out.print(" "+partizionamento[i]);
	    }
	}
	
	private int[] randPartA;
	private int[] randPartB;
	private int[][] matrix;
	private int numeroCilcli;
	private int[] optimalPartitionA;
	private int[] optimalPartitionB;
	private int costo;
	
	public LKBipartitionEnhanced(int[][] matrice)
	{
		this.matrix = getNewMatrice( matrice );
		this.numeroCilcli=1;
		this.costo=-1;
		this.calcola();
	}
	
	public LKBipartitionEnhanced(int[][] matrice, int numCicli)
	{
		this.matrix= getNewMatrice( matrice );
		this.numeroCilcli=numCicli;
		this.costo=-1;
		this.calcola();
	}
	
	private void calcola()
	{
		this.calcolaRandomPartition();
		LKBipartition lk=new LKBipartition(matrix, getNewVettore(randPartA), getNewVettore(randPartB));
		costo = lk.getCosto();
		optimalPartitionA = lk.getPartitionA();
		optimalPartitionB = lk.getPartitionB();
		
		
		int[] partA = getNewVettore( optimalPartitionA);
		int[] partB = getNewVettore( optimalPartitionB);
		for (int i=0 ; i< numeroCilcli ;i++)
		{
			// Calcolo la nuova soluzione iniziale
			// facendo lo swap dei sottoinsiemi
			Random rand=new Random();
			int index = rand.nextInt(optimalPartitionA.length);
			for (int k=0; k< optimalPartitionA.length; k++)
			{
				if ( k<index )
				{
					randPartA[k]=partA[k];
					randPartB[k]=partB[k];
				}
				else
				{
					randPartA[k]=partB[k];
					randPartB[k]=partA[k];
				}
			}
			lk=new LKBipartition(matrix, getNewVettore(randPartA), getNewVettore(randPartB));
			//lk=new LKBipartition(matrix, randPartA, randPartB);
			int costoAttuale = lk.getCosto();
			partA = getNewVettore( lk.getPartitionA());
			partB = getNewVettore( lk.getPartitionB());
			if (costoAttuale< costo)
			{
				costo = costoAttuale;
				optimalPartitionA = getNewVettore( partA );
				optimalPartitionB = getNewVettore( partB );
			}
		}
	}
	
	private void  calcolaRandomPartition()
	{
		int cardinalita=matrix.length;
		Set<Integer> setA=new HashSet<Integer>();
		Set<Integer> setB=new HashSet<Integer>();
		for (int i=0; i<cardinalita ; i++)
		{
			setA.add(new Integer(i));
		}
		do
		{
			int[] vet=getVettore(setA);
			Random rand=new Random();
			int indice=rand.nextInt(vet.length);
			int value=vet[indice];
			setA.remove(new Integer(value));
			setB.add(new Integer(value));
		}
		while(setA.size() != setB.size() );
		this.randPartA = getVettore( setA );
		this.randPartB = getVettore( setB );
	}
	
	public int getCosto() {
		return costo;
	}

	public int[] getOptimalPartitionA() {
		return optimalPartitionA;
	}

	public int[] getOptimalPartitionB() {
		return optimalPartitionB;
	}
	
	public int[] getPartizionamento()
	{
		int[] result=new int[matrix.length];
		for(int i=0; i< result.length; i++)
		{
			result[i]=0;
		}
		for(int i=0; i< optimalPartitionB.length; i++)
		{
			int value=optimalPartitionB[i];
			result[value]=1;
		}
		return result;
	}

	private int[] getVettore(Set<Integer> set)
	{
		int[]result=new int[set.size()];
		int i=0;
		for(Object object: set.toArray() )
		{
			int value=((Integer)object).intValue();
			result[i]=value;
			i++;
		}
		return result;
	}
	
	private int[] getNewVettore(int[] vett)
	{
		int[] result=new int[vett.length];
		for (int i=0;i<vett.length;i++)
		{
			result[i]=vett[i];
		}
		return result;
	}
	
	private int[][] getNewMatrice(int[][] matrice)
	{
		int[][] result=new int[matrice.length][matrice.length];
		for (int i=0; i<matrice.length; i++)
		{
			for (int j=0; j< matrice.length ; j++)
			{
				result[i][j]=matrice[i][j];
			}
		}
		return result;
	}
	
	private void printVettore(String descrizione, int[] vett)
	{
		System.out.println();
		System.out.println(descrizione);
		for(int i=0; i<vett.length ; i++)
		{
			System.out.print(" "+vett[i]);
		}
		System.out.println();
	}

}
